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)

5
votes
2answers
402 views

Applications of generating functions to number theory

I am familiar (at least at a cursory level) with the extensive role generating functions play in the theory of partitions. What are some other prominent applications of generating functions to number ...
2
votes
1answer
76 views

How to find $\sum_{d\mid n}(w(d)w(\frac{n}{d}))$?

i) $w(n)$ is the prime divisor count function. For example $w(6)=2$ ii) Let prime factorization of $n=p_{1}^{a_{1}}p_{2}^{a_{2}}.....p_{w(n)}^{a_{w(n)}}$ iii) Lets define this function. ...
1
vote
2answers
78 views

Probability of number formed from dice rolls being multiple of 8

A fair 6-sided die is tossed 8 times. The sequence of 8 results is recorded to form an 8-digit number. For example if the tosses give {3, 5, 4, 2, 1, 1, 6, 5}, the resultant number is $35421165$. ...
1
vote
2answers
77 views

How many strings of 8 digits end with an even digit?

So there are $10$ combinations for each digit except the last which has 5 possibilities ($0,2,4,6,8$). Thus $10*10*10*10*10*10*10*5=50000000$ combinations right? As a follow up, how many strings of 8 ...
2
votes
3answers
31 views

Find the formula for the given sum of series

Find the sum of the series: $$\sum_{i=2}^{n}\binom{i}{2}= \,^{2}C_{2}+\cdots+\,^{n}C_{2}$$ I did try expanding it and see if I could simplify it further.I am unable to find a formula for it? Can ...
1
vote
2answers
33 views

Stirling Numbers of the First Kind and $S_n$.

I know that, on the one hand, if $s(n, p)$ denotes the unsigned Stirling Numbers of the First Kind, then $(x)_n=\displaystyle\sum_{p=0}^n s(n, p)x^p$, where $(x)_n=x(x-1)\cdots(x-n+1)$. It follows ...
0
votes
2answers
44 views
0
votes
2answers
63 views

permutation problem: cycle representation

Let $n$ be an odd number. Let $C_n$ be the set of permutations $\pi$ of $[n]$ whose cycle representation has only one cycle. Let $\pi,\sigma\in C_n$. Prove that their composition $\pi\sigma$ has an ...
2
votes
1answer
50 views

Probability of drawing 4 green balls from an urn when you're the last person to draw

An urn contains 24 balls, 8 of them being white, 8 green and 8 black. There are 6 people sequentially drawing these balls out of the urn (without replacement), with every person drawing 4 balls, and ...
1
vote
1answer
60 views

Algorithm to find all feasible partition of a set

By feasible I mean all the sets of the partition belongs to a predefined feasible sets. For example, I what to find a partition of {1,2,3}, and only sets in S = {{1,2}, {1,3}, {1}, {2}, {3,4,5}} is ...
1
vote
1answer
74 views

How many ways move n pies to m distances?

A table size $1\times (m+n)$ squares. Give $n$ pies on the $n$ first squares. Now, I want move $n$ pies to the end of table by $m.n$ steps ($m$ steps for each pie), satify conditions one pie only move ...
0
votes
1answer
30 views

Exercises in combinatorics

I'm always having problem with this type of question : 1). Can the set ${1,2,...,2010}$ be expressed as the disjoint union of $A_{1},A_{2},...,A_{n}$ such that a). Each $A_{i}$ contains the same ...
4
votes
2answers
113 views

Fraction Problem. 3rd grader question got parents thinking

So our nine year old son comes home from 3rd grade and tells us an amazing thing happened in school today. He was playing a math game with his friend and they got the same score two times in a row! ...
1
vote
0answers
58 views

Counting bit string with fixed values

I would like to run this questions with stack: How many bit strings of length 33 are there that start with 1010, end with 0101, and contain exactly 11 zeros. The amount of fixed bits are 8. ...
1
vote
1answer
89 views

Balls. Combinations.

A jar contains 17 red balls and 22 blue balls. How many ways are there to choose, without replacement, 8 balls from this jar. I have two answers, but they both seem right to me. Could some explain ...
0
votes
2answers
200 views

How many bit strings of length $7$ either begin with two $1's$ or end with three $1's$?

So for the first case (beginning with 2 $1's$) there are: $2*2*2*2*2=32$ ways Second case (end with three $1's$): $2*2*2*2=16$ And then we can just sum it $32+16=48$ different bit string of length 7 ...
0
votes
2answers
19 views

Combinations questions

a. How many different 4 letter codes can there be? b. What if letters cannot be repeated? c. What if, in addition, 2 of the letters are x and y? For a, it would simply be $26*26*26*26=456976$ For ...
1
vote
1answer
19 views

Question over combinations

A t-shirt is being sold in 8 colors, 4 sizes, collared or tee, and long sleeve or short sleeve. a. How many different shirts are being sold? b. What if collared shirts only come in 5 colors and 2 ...
0
votes
0answers
10 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
27 views

permutation with four fixed numbers [closed]

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 ...
1
vote
1answer
110 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
39 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
114 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
23 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
37 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
35 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 ...
2
votes
4answers
70 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
56 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
44 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
61 views

What exactly does $\vdash_T G_T \leftrightarrow \lnot \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
76 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
81 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
21 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
113 views

Combinatoric Graph [closed]

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 ...
1
vote
3answers
84 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
93 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. ...
1
vote
2answers
100 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
37 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
33 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
35 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
88 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
128 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
44 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
70 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
42 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
32 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
46 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
1answer
55 views

Existence of 1-factor in a connected graph and its connctivity

Let $G$ be a connected graph of even order( greater than or equal to 2k) such that every set of $k-1$ independent edges belong to a $1-factor$ of the graph. Then the graph is $k$-connected. If the ...
2
votes
3answers
198 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 ...
2
votes
0answers
45 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$?