This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

0
votes
0answers
5 views

How many partitions of $N$ are there into $n$ non-negative parts $c_k$ such that $\sum_{k=1}^n c_k = N$ and $\sum_{k=1}^n kc_k = M$??

So when coming up with a recursive solution to a counting problem of placing 1's into an $N \times N$ matrix ($N$ even) so that every row and every column has exactly $N/2$ 1's, my recursive ...
0
votes
2answers
21 views

permutation with four fixed numbers [on hold]

My problem appeared to be part of permutation but not sure. I have a fixed length of 4 digits with 2 variable digits. say i have ...
0
votes
1answer
48 views

Number of surjective functions from $\{1,2,…,n\}$ to $\{a,b,c\}$

Ok so following questions are given in my text book Let $A = \{1, 2, 3,...., n\}$ and $B =\{a, b, c\}$ then the number of functions form $A$ to $B$ that are onto is. I have no idea how to find ...
3
votes
0answers
24 views

A question on combinations of a set of numbers

I have the set of the first $n$ primes $\{2,3,5,\ldots,p_n\}$. There are $n^n$ ways of selecting $n$ numbers from this set. Each combination has a number ($C_k$) associated with it and it is the ...
1
vote
3answers
37 views

Error solving “stars and bars” type problem

I have what I thought is a fairly simple problem: Count non-negative integer solutions to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 23$$ such that $0 \leq x_1 \leq 9$. Not too hard, right? ...
2
votes
2answers
16 views

Probability Question - team draw from field of 32

For a sport tournament where two-man teams are drawn from a sample of 32 without replacement, what is the probability of two men being on the same team one year and then two years in a row?
1
vote
2answers
32 views

A question on the expansion of $(1-x)^n$

Suppose we are given $f(x)=(1-x)^n$, where $x \in (0,1)$, and $n$ is an positive integer. We can rewrite $f(x)$ as \begin{equation} f(x) = \sum_{i=0}^n \binom{n}{i} (-x)^i = 1 - nx + ...
0
votes
1answer
17 views

Construct matrix of ones and zeros based on sequences

We are given ($a_1,a_2,....,a_m$) and ($b_1, b_2,....,b_n$) sequences with non-negative integers. Decide whether it's possible and if it is construct a matrix $\Re^{m x n}$ of ones("1") and ...
0
votes
0answers
14 views

How to get best series of occurances out of pairs and their %?

I am trying to play with lottery numbers (I know it's statisics and all - and the numbers don't really mean anything, still, it's nice to play with numbers) I have a list of pairs of numbers, each ...
2
votes
4answers
61 views

Looking for combinatorial proof for identity $n! = 1 \cdot 1! + 2\cdot 2! … (n-1) \cdot (n-1)! + 1$ [duplicate]

I am looking for a combinatorial proof of the following identity $$ n! = 1 + \sum_{i=1}^{n-1} {i \cdot i!} $$ I appreciate your help!
1
vote
1answer
26 views

Envelopes and Mailboxes

We suppose $n$ and $p$ are two positive integers. A) In how many ways can you divide $p$ identical envelopes in $n$ mailboxes? (Each mailbox can hold several envelopes at the same time) B) In how ...
1
vote
3answers
27 views

explanation for a combinatorial identity involving the binomial coefficient

I am looking for an intuitive explanation for the identity: $$\binom{n}{h}\binom{n-h}{k} = \binom{n}{k}\binom{n-k}{h}$$ Thanks!
1
vote
1answer
32 views

What exactly does $\vdash_T G_T \leftrightarrow \not \exists y$ Prf$(\ulcorner G_T \urcorner, y)$ mean?

To me this translates to: $G_T$ is provable in $T$ if and only if there doesn't exist a $y$ such that $y$ is a witness to the provability of $\ulcorner G_T \urcorner$. But I'm not entirely sure what ...
1
vote
1answer
32 views

MathCounts 1993 National Sprint #28

Here is the problem: In a small town of 100 men, 85 are married, 70 have a telephone, 75 own a car, and 80 own their own home. On this basis, what is the smallest possible number of men who are ...
2
votes
0answers
16 views

number of ways to split n distinguishable objects into k indistinct sets - allowing for sets with 0 objects

After throughout searching both on this site and others I cannot seem to find a good explanation of how to solve this problem. I understand that if the objects are indistinguishable then it is a ...
3
votes
0answers
15 views

4-net in binary hypercube

Consider a binary hypercube $\mathbb{F}_2^n$. What is the largest size of a subset $S$ such that $d(x,y)\geq 4$ for all $x,y\in S$ ($x\neq y$), where $d(x,y)$ is the Hamming distance between $x$ and ...
1
vote
2answers
47 views

Combinatoric Graph [on hold]

Draw a graph whose nodes are the subsets of {a,b,c} and for which two nodes are adjacent if and only if they are subsets that differ in exactly one element? I'm having a really hard time understanding ...
-3
votes
1answer
24 views

Generating Functions [on hold]

Write a generating function that models the number of distributions of r identical balls into 5 distinct boxes if each box has between two and seven balls. Then find the coefficient that gives the ...
1
vote
3answers
74 views

Integer solutions Help

How many integer solutions are there to $$x_1 +x_2 + \text{ ... }+x_5 =31 \;\; \text{ with } \; \; x_i \geq i, \;\; i=1,2,3,4,5$$ I tried it and got $C(20,16)$ but I don't really think that is ...
0
votes
2answers
44 views

Exponential Generating function

Use an exponential generating function to determine how many ways there are to make an r-arrangement of pennies, nickels, dimes and quarters with at least one penny and an odd number of quarters. ...
0
votes
0answers
23 views

compute the homology group

Let G be a finite connected graph. Let K be a 2-dim complex s.t. (1) K has same 1 skeleton (2) 2dim reduced homology of K is zero (3) 1dim reduced homology of K is Z/mZ. Then find ...
1
vote
2answers
27 views

How many 6 letter words can be made with these conditions?

The letters that can be used are A, I, L, S, T. The word must start and end with a consonant. Exactly two vowels must be used. The vowels can't be adjacent.
0
votes
1answer
29 views

How many ways of combining 4 fruits, repeting at most 1 twice?

another simple question - How many ways do I have of picking 4 fruits among a menu of 8 types of fruits, repeting at most 1 type twice? This is a simple exercise, but I got really stuck at it. ...
0
votes
0answers
34 views

acyclic augmentation, cycle-intersection matrix, and number of spanning trees

Let G be a finite connected graph. Let K be a 2-dim any acyclic augmentation of G. Then determinant of cycle-intersection matrix is number of spanning tree in G
0
votes
0answers
23 views

A nowhere zero point in a linear mapping and Research Resources

Conjecture: If $\mathbb{F}$ is a finite field with at least 4 elements and $A$ is an invertible $n\times n$ matrix with entries in $\mathbb{F}$, then there are column vectors $x,y \in \mathbb{F^n}$ ...
1
vote
1answer
28 views

Possible arrangments Letters?

How many arrangements are possible of the letters in EZPZ I CAN DO IT, which has five vowels (A, E, I, I, O) and seven consonants (C, D, N, P, T, Z, Z). a) if there are no restrictions, b) if ...
0
votes
1answer
18 views

Marble Probability

A bag contains 3 red marbles, 3 green ones, 1 lavender one, 6 yellows, and 4 orange marbles. How many sets of five marbles include either the lavender one or exactly one yellow one but not both ...
3
votes
2answers
119 views

A combinatorial question. Is this a known result, false, or open?

Let $X$ be a set of $n-1$ elements. Does there exist a family $S_1,S_2...S_n\in 2^X$ such that $$|S_i\cap S_j|\le 1$$ and $$|\overline S_i\cap \overline S_j|\le 1$$? That is, neither the sets ...
0
votes
2answers
39 views

A question in combinatorics

What is the possible number of ways in which 8 digit numbers can be made from 1,1,1,2,2,3,4,4 such that odd numbers do not occupy odd places ?
2
votes
1answer
30 views

Proving that if $n\times n$ Hadamard matrix exists, then 4 divides $n$

Im looking for an explanation of the following: a standard way to prove that, if there exists Hadamard matrix of dimension $n > 2$, then $4|n$, is to suppose that without loss of generality every ...
1
vote
2answers
36 views

Inequality with two binomial coefficients

I am having trouble seeing why $$ \binom{k}{2} + \binom{n - k}{2} \le \binom{1}{2} + \binom{n - 1}{2} = \binom{n - 1}{2} $$
0
votes
0answers
27 views

Probability: Disease and Diagnosis

The probability of occurrence of a certain disease in a population is $1/101$. A diagnostic test has $9$ out of $10$ chances to detect the disease when the tested subject is actually affected. On the ...
1
vote
2answers
26 views

How do I calculate variance for sum of dice?

I'll post my work, but I'm not sure how to calculate variance. The question asks for the expected sum of 3 dice rolls and the variance. I think I got the expected sum. Any help would be awesome :) ...
2
votes
2answers
56 views

Prove that there are two frogs in one square.

A certain chessboard is infinite in size. There is a frog sitting in the center of every square. After a certain time, all the frogs jump such that They may jump to any possible square in the ...
0
votes
0answers
37 views

No of ways to reach out there

Suppose there are 12 stations between two places. A train starting at one of these two places stops in exactly four of these stations before reaching the other of these two places in such a way that ...
2
votes
0answers
37 views

Uniqueness of projective plane of order 5

Is there a slick way to see the uniqueness of projective plane (equivalently, an affine plane) of order $5$?
0
votes
1answer
39 views

Probability: put 20 distinct balls randomly in 12 urns

You put 20 distinct balls randomly into 12 urns. What is the probability of having 3 urns with 4 balls each and 4 urns with 2 balls each (the other 5 urns are left empty). For my sample space I have: ...
3
votes
1answer
50 views

How to evaluate this sum 2?

$\displaystyle\sum_{x+y+z=2014}xy^2z^3$ $\quad , x,y,z\in\mathbb{N}$ I think it maybe use combinatorial method.
0
votes
1answer
13 views

Simple question about choosing items from a box

Let's say I have a box of twelve balls and eight are blue and the rest red. When I choose seven balls at random, what is the probability of getting exactly two blue balls? I know it's a fraction ...
1
vote
1answer
28 views

How many different possibilities for ordering distinct sorted elements

Quick question - How many ways do we have to place $m$ men and $w$ women in a queue, all with different heights, such that all men are placed in ascending order of heights between themselves and all ...
0
votes
1answer
47 views

Placing two queens on an $n \times m$ chessboard

I want to find the number of ways in which two queens can be placed on a chessboard so that they can attack each other. two queens can attack each other on a row, a column or on same diagonal just ...
1
vote
6answers
208 views

Prove that $\sum_{k=0}^n k^2{n \choose k} = {(n+n^2)2^{n-2}}$

Prove that: $$\sum_{k=0}^n k^2{n \choose k} = {(n+n^2)2^{n-2}}$$ i know that: $$\sum_{k=0}^n {n \choose k} = {2^n}$$ how to get the (n + n^2)?
1
vote
1answer
23 views

What's wrong with this recursion of counting codes of length $n$ formed by $a$, $b$, and $c$ such that no three consecutive letters are distinct

I found the following problem in a combinatorics book and gave it a try. Let $B_n$ denote the set of codes of length $n$ formed by using the letters $a$, $b$, and $c$, none of which contains three ...
-2
votes
1answer
49 views

Finding $E[X^2]$ if $E[X] = \frac{\pi k}{4}$ [duplicate]

We try to approximate $\pi$ by choosing random points in a square and seeing if they lie within the inscribed circle. The probability that a point is in the circle is $\frac{\pi}{4}$. Suppose we ...
2
votes
1answer
63 views

Possible shorter solution to this problem?

How many pairs of diagonals of a regular decagon are parallel? The answer is $45$, and is computed via: $$5\binom{4}{2} + 5 \binom{3}{2}$$ which comes as a result of fixing one vertex and ...
1
vote
1answer
32 views

Combinations and Probability Problems

I try this problem and I got $\binom{50}{20} * \binom{30}{20} * \binom{10}{10} = 1.416 * 10^{21}$ . I just want to make sure I have the right idea for this problem. In a medical experiment involving ...
1
vote
1answer
35 views

Probability and Combinations

In a family with 6 children, a. What is the probability of having three children of each sex? b. What is the probability of having four of one sex and two of the other sex? I know in this problem ...
1
vote
3answers
70 views

Proof that $ p $ | ${ p^n \choose k } $ for any prime $p$ and $ k < p^n$

I know how to prove the fact that $ p$ | ${ p \choose k } $ (when writing it as a fraction, $p$ cannot be divided by any of the $1\times2\times...\times k$ or $1\times2\times...\times(p-k)$ because ...
1
vote
2answers
54 views

Combinatorics help

Say there are infinite marbles of k colors and we have to pick n marbles out of them. The marbles must be picked up such that we have at least k different colored marbles. What are the possibility. ...
-2
votes
1answer
34 views

Selecting red and white balls [on hold]

A box contains $4$ white and $3$ red balls if $x$ denotes the number of red balls in three draws with replacement. Find the probability distribution of $x$.